1565. Игра с пол-потолком
Теорема. Для двух целых
чисел x и k всегда существуют такие целые p и q,
что
x = p
+ q
Это довольно
известная теорема, но мы не просим Вас её доказывать. Мы хотим Вас попросить
сделать кое-что попроще! Зная значения целых x и k, Вы должны найти
такие целые p и q, которые удовлетворяют заданному уравнению.
Вход. Первая строка содержит количество
тестов t (1 ≤ t ≤
1000). Каждая из следующих t строк содержит
два положительных целых числа x и k. Известно, что x и k не больше 108.
Выход. Для
каждого теста выведите в отдельной строке два целых числа p и q. Если существует
несколько пар чисел p и q, удовлетворяющих условию, то выведите
любую. Известно, что значения p
и q
являются 64-битными целыми числами.
|
Пример входа |
Пример выхода |
|
3 5 2 40 2 24444
6 |
1 1 1 1 0 6 |
РЕШЕНИЕ
расширенный
алгоритм Евклида
Анализ алгоритма
Если x
нацело делится на k, то = = x / k.
Выбрав p = 0, q = k, получим: 0 * (x / k) + k
* (x / k) = x.
Пусть x
не делится на k. Если n = , то m = = n + 1.
Поскольку НОД(n , m) = НОД(n , n + 1) = 1, то
исходя из расширенного алгоритма Евклида, существуют такие целые t и u,
что 1 = tn + um. Помножив равенство на x, получим x
= xtn + xum, откуда p = xt, q = xu.
Пример
В первом тесте x = 5, k = 2. Значение x
не делится на k нацело. Вычислим n = 
= 2, m = 
= 3. Решением
уравнения 2t + 3u = 1 будет пара (t, u) = (-1, 1). Умножим
уравнение на x = 5. Решением уравнения 2p + 3q = 5 будет пара (p,
q) = (5t, 5u) = (-5, 5). Имеет
место соотношение:
5 = (-5)
* + 5 * = (-5) * 2 + 5 * 3 =
-10 + 15
Реализация
алгоритма
При вычислении
используем 64-битовый целый тип long long. Для простоты
использования переопределим тип:
typedef long
long i64;
Функция gcdext представляет
собой расширенный алгоритм Евклида.
void
gcdext(i64 a,i64 b, i64 *d, i64 *x, i64 *y)
{
i64 s;
if (b == 0)
{
*d = a; *x = 1; *y = 0;
return;
}
gcdext(b,a % b,d,x,y);
s = *y;
*y = *x - (a / b) * (*y);
*x = s;
}
Основная часть
программы. Читаем количество тестов. Для каждого теста вводим значения x
и k.
scanf("%d",&tests);
while(tests--)
{
scanf("%lld %lld",&x,&k);
Если x делится на k, то
устанавливаем p = 0, q = k.
if (x % k ==
0) { p = 0; q = k;}
else
{
Иначе вычисляем n
= и m = , запуская расширенный алгоритм Евклида. Он находит такие t
и u, что 1 = tn + um. Далее находим p = xt, q
= xu и выводим результат.
n = (int)floor(1.0
* x / k); m = (int)ceil(1.0 * x / k);
gcdext(n,m,&g,&t,&u);
p = t * x; q = u * x;
}
printf("%lld
%lld\n",p,q);
}